# 【一】定义
# ● 布隆过滤器（Bloom Filter） 是一种空间效率极高的概率型数据结构，用于测试一个元素是否在一个集合中。
# ● 它的优点是空间效率和查询时间都远超过一般的算法，缺点是有一定的误识别率和删除困难。
# 【二】原理
# ● 布隆过滤器使用位数组（bit array）和一系列的哈希函数。
# ● 当你向布隆过滤器中添加一个元素时，布隆过滤器会使用多个哈希函数对这个元素进行哈希计算，得到一系列哈希值，然后将这些哈希值对应的位数组中的位设置为1。
# ● 当需要查询一个元素是否存在于布隆过滤器中时，同样使用这些哈希函数对元素进行哈希计算
#   ○ 如果所有哈希值对应的位都是1，那么认为该元素存在于布隆过滤器中；
#   ○ 如果有任何一个哈希值对应的位是0，那么认为该元素不存在于布隆过滤器中。
# ● 需要注意的是，布隆过滤器可能会产生误报，即认为某个不存在的元素存在于过滤器中。
# ● 这是因为不同的元素可能通过哈希计算得到相同的哈希值，导致它们的位都被设置为1。
# ● 但是，布隆过滤器不会产生漏报，即如果某个元素确实存在于过滤器中，那么查询结果一定会返回存在。

# 【三】Scrapy框架中的去重过滤器源码
from scrapy.core.scheduler import BaseScheduler

'''

class BaseDupeFilter:
    @classmethod
    def from_settings(
        cls: Type[BaseDupeFilterTV], settings: BaseSettings
    ) -&gt; BaseDupeFilterTV:
        return cls()
    
    def request_seen(self, request: Request) -&gt; bool:
        return False

    def open(self) -&gt; Optional[Deferred]:
        pass

    def close(self, reason: str) -&gt; Optional[Deferred]:
        pass

    def log(self, request: Request, spider: Spider) -&gt; None:
        """Log that a request has been filtered"""
        pass
'''

# 原理
# 创建一个列表 列表中一开始是空的
# 请求过一个地址 就向其中增加一个地址 [1,2,3,4,5]

# 每一次请求进来的时候都要经过这个列表的判断  判断一下当前请求是否 在已经请求过的列表中
# 一种是在  返回True 直接 pass 当前请求
# 一种是不在 如果 False ---&gt; 把当前请求扔到列表中存起来

# scrapy 内置的过滤方法要比我们现在将的要复杂的多 内置使用的是布隆过滤器

# 【四】布隆过滤器的应用场景
# 在进行用户注册时候一般情况下用户名是不允许重复的

# 所有的用户名都存在数据库 MySQL 中
# 你怎么去校验 用户名是不允许重复的
# 从数据库中把所有的用户名都查出来 查出来以后在进行成员运算判断  1亿   1G

# 于是出现了一个数据结构 叫布隆过滤器 空间小但是数据量可以很大 500MB
# 内存占的小但是可以容纳的数据多

# 可以将所有人的姓名在启动的那一刻 获取出来 扔到布隆过滤器里面
# 下一个人注册用户名的时候直接去布隆过滤器里面查

# 【五】使用
"""
from scrapy.utils.request import RequestFingerprinter
from scrapy import Request

# 因为每一个人的指纹都是独一无二的
# 请求指纹信息

# 【1】创建一个指纹对象
finger = RequestFingerprinter()

# 【2】使用 scrapy 中的 Request 发请求
request_one = Request(url="https://www.baidu.com")
request_two = Request(url="https://www.jd.com")

# 【3】获取到请求对应的指纹对象
finger_one = finger.fingerprint(request_one).hex()
finger_two = finger.fingerprint(request_two).hex()

print(finger_one)
print(finger_two)
'''
27cd411aeee77be9d762fa0a6f9dcf49cea6175d
6611edff4c837a630213549c817d8fd9d51d88ee
'''
"""

# 【六】第三方的布隆过滤器
# 【1】安装
# pip install pybloom-live

# 【2】使用
from pybloom_live import ScalableBloomFilter, BloomFilter

# 【3】向布隆过滤器中增加容量和误差
# initial_capacity - 初始的过滤器容量
# error_rate - 期望的错误率
# mode - 过滤器模式，可选的值有：
# ScalableBloomFilter.SMALL_SET_GROWTH：slower, but takes up less memory 很慢但是占用更少的内存
# ScalableBloomFilter.LARGE_SET_GROWTH：faster, but takes up more memory faster 更快，但是需要更多的内存
bloom = ScalableBloomFilter(initial_capacity=100, error_rate=0.001, mode=ScalableBloomFilter.LARGE_SET_GROWTH)

# 【4】向布隆过滤器中添加数据
# 向布隆过滤器中添加 1w 条数据判断，某条数据是够在其中
url_one = "https://www.baidu.com"
url_two = "https://www.jd.com"

bloom.add(url_one)
bloom.add(url_two)

# 【5】测试当前数据是否在布隆过滤器内部
print(url_one in bloom)
print("https://www.tianmao.com" in bloom)
